home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 10052 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.9 KB
  1. Path: anvil.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: C uses simple LALR parsing?
  5. Date: 14 Mar 1996 17:18:13 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4iagglINNdu7@anvil.ugrad.cs.ubc.ca>
  8. References: <4i9ilq$92a@sargas.omicron.se>
  9. NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca
  10.  
  11. In article <4i9ilq$92a@sargas.omicron.se>,
  12. Elias Martenson <elias@omicron.se> wrote:
  13.  >This question has been subject to major debate among me and my firends:
  14.  >
  15.  >Does the C standard specify what kind of parser to use? If it uses
  16.  >(and is does seem that at least AT&T C and GCC does) a simple
  17.  >LALR parser it would mean that the following expression:
  18.  >
  19.  >    a+++++b
  20.  >
  21.  >Yields:
  22.  >
  23.  >    SYMBOL INCR INCR ADD SYMBOL
  24.  >
  25.  >Instead of the desired result (which is acieved when doing a++ + ++b):
  26.  >
  27.  >    SYMBOL INCR ADD INCR SYNBOL
  28.  >
  29.  >Is it legal for a C compiler to parse the expression like the last
  30.  >example?
  31.  
  32. The distinction you are describing has nothing to do with LALR(1) parsing, and
  33. everything with _lexical analysis_.
  34.  
  35. Lexical analysis is based on regular expressions, which are weaker than
  36. LR grammars (a regular expression is basically a grammar which is only right
  37. recursive---a non terminal symbol never appears between two terminals in any
  38. production), hence it cannot match things like nested parentheses. 
  39.  
  40. The answer to your question is, yes, the C standard lexical rules are indeed
  41. unambigous. The expression 'a+++++b' will be tokenized as 'a ++ ++ + b'.
  42.  
  43. The rule used is simple: extract from the input the longest lexeme that matches
  44. the regular expression pattern. When faced with '+++++++', the lexical analyzer
  45. will extract '++' rather than '+'. Both are matching tokens, but the first one
  46. is longer.
  47.  
  48. The compiler will not figure out the alternate scan just to eliminate the
  49. syntax error.
  50. -- 
  51.  
  52.